JZ65 矩阵中的路径

https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6

这题考察深度搜索，需要注意的是，深度搜索不要试图去展开递归的过程，只需要知道它可以拿到一个结果就行了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        if (word.length() == 0) return true;
        if (matrix.length < 1 && word.length() > 0) return false;
        if (matrix[0].length < 1 && word.length() > 0) return false;
        
        char[] arr = word.toCharArray();
        
        // 因为可能在矩阵中任意一个位置，所以得用二维数组检查
        for(int y = 0; y < matrix.length; y++) {
            for(int x = 0; x < matrix[0].length; x++) {
                if (checkDir(matrix, arr, x, y, 0)) return true;
            }
            
        }
        
        return false;
    }
    
    // 检查四个方向是否满足，这题主要麻烦在它可能会回溯
    private boolean checkDir(char[][] matrix, char[] target, int x, int y, int index) {
        // 边界
        if (y >= matrix.length || y < 0 || 
            x >= matrix[0].length || x < 0 || 
            matrix[y][x] != target[index]) return false;
        
        // 遍历到目标数组的最后一个时返回 true
        if (index == target.length - 1) return true;
        
        // 这里覆盖原来的路径，避免回溯
        char temp = matrix[y][x];
        matrix[y][x] = '#';
        
        // 检查四个方向
        boolean res = checkDir(matrix, target, x + 1, y, index + 1) || // right
            checkDir(matrix, target, x - 1, y, index + 1) || // left
            checkDir(matrix, target, x, y + 1, index + 1) || // up
            checkDir(matrix, target, x, y - 1, index + 1); // down
        
        // 结束递归
        matrix[y][x] = temp; // 可能绕一圈回来了，所以需要变回原本的字符
        
        // 检查四个方向
        // 这里应该使用断路器
        return res;
    }
}